package com.peng.leetcode.backtracking;

import java.util.LinkedList;
import java.util.Queue;

/**
 * NumIslands
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围
 * <p>
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 *
 * @author: lupeng6
 * @create: 2020/12/29 11:22
 */
public class NumIslands {

    public static void main(String[] args) {
//        char[][] grid = {{'1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1','0','1','1'},{'0','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','0'},{'1','0','1','1','1','0','0','1','1','0','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','0','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','0','1','1','1','1','1','1','0','1','1','1','0','1','1','1','0','1','1','1'},{'0','1','1','1','1','1','1','1','1','1','1','1','0','1','1','0','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','1','1'},{'1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'0','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','0','1','1','1','1','1','1','1','0','1','1','1','1','1','1'},{'1','0','1','1','1','1','1','0','1','1','1','0','1','1','1','1','0','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','0'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','0','0'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'}};
        char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
//        System.out.println(new NumIslands().numIslands1(grid));
        System.out.println(new Solution().numIslands(grid));
    }

    private boolean[][] marked;

    private int[][] operations = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int numIslands(char[][] grid) {
        this.marked = new boolean[grid.length][grid[0].length];
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            char[] chars = grid[i];
            for (int j = 0; j < chars.length; j++) {
                if (grid[i][j] == '1' && !marked[i][j]) {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid, int x, int y) {
        if (!isArea(grid, x, y) || grid[x][y] != '1' || marked[x][y]) {
            return;
        }
        marked[x][y] = true;
        for (int[] operation : operations) {
            dfs(grid, x + operation[0], y + operation[1]);
        }
    }

    public static boolean isArea(char[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }


    ////////////////////////////广度优先查找//////////////////////////////////

    private boolean[][] visited;

    public int numIslands1(char[][] grid) {
        this.visited = new boolean[grid.length][grid[0].length];
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            char[] chars = grid[i];
            for (int j = 0; j < chars.length; j++) {
                if (!visited[i][j] && chars[j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void bfs(char[][] grid, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            if (grid[xy[0]][xy[1]] == '1') {
                visited[xy[0]][xy[1]] = true;
                for (int[] operation : operations) {
                    int newX = xy[0] + operation[0];
                    int newY = xy[1] + operation[1];
                    if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && !visited[newX][newY] && grid[newX][newY] == '1') {
                        queue.offer(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
    }


    ////////////////////////////并查集//////////////////////////////////


    public static class Solution {

        private int rows;
        private int cols;

        public int numIslands(char[][] grid) {
            rows = grid.length;
            if (rows == 0) {
                return 0;
            }
            cols = grid[0].length;

            // 空地的数量
            int spaces = 0;
            UnionFind unionFind = new UnionFind(rows * cols);
            int[][] directions = {{1, 0}, {0, 1}};
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == '0') {
                        spaces++;
                    } else {
                        // 此时 grid[i][j] == '1'
                        for (int[] direction : directions) {
                            int newX = i + direction[0];
                            int newY = j + direction[1];
                            // 先判断坐标合法，再检查右边一格和下边一格是否是陆地
                            if (newX < rows && newY < cols && grid[newX][newY] == '1') {
                                int index = getIndex(i, j);
                                int index1 = getIndex(newX, newY);
                                unionFind.union(index, index1);
                            }
                        }
                    }
                }
            }
            return unionFind.getCount() - spaces;
        }

        private int getIndex(int i, int j) {
            return i * cols + j;
        }

        private class UnionFind {
            /**
             * 连通分量的个数
             */
            private int count;
            private int[] parent;

            public int getCount() {
                return count;
            }

            public UnionFind(int n) {
                this.count = n;
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            private int find(int x) {
                while (x != parent[x]) {
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            public void union(int x, int y) {
                int xRoot = find(x);
                int yRoot = find(y);
                if (xRoot == yRoot) {
                    return;
                }

                parent[xRoot] = yRoot;
                count--;
            }
        }
    }

}
